1. Field of Invention
This invention relates to methods and apparatus for class sensitive queuing.
2. Description of Related Art
Data transmitted in a network is often placed in a serial queue for routing and forwarding. The order that the data is queued is irrespective of the subscribers"" subscription relationship with the network service provider. Thus, there are no provisions in the network routing and forwarding processes for making distinctions based on subscribers"" subscription requirements. In fact, queuing techniques in general do not address subscription related issues. Accordingly, new technology is needed.
This invention provides a class queuing system where data is placed in queues distinguished by class. The class queuing system distinguishes one class from another based on desired characteristics of a host process such as a network process. For example, in a network environment, the desired characteristics may be expressed in network parameters such as transmission capacity (bandwidth), transmission throughput, end-to-end delay, quality of transmission or error rate, for example. Classes may be distinguished from each other by specifying minimum bounds of the above parameters so that data transmission for each of the classes may be guaranteed performance above the specified minimum bounds.
The class queuing system establishes groups of class queues which may be implemented using a single or multiple memories. Physical grouping of the class queues is not required because the complete class queuing system may be implemented via memory mapping, for example. However, for ease of visualization and discussion, related figures illustrate the group concept to show the functions of the invention.
Each of the groups corresponds to one output port that is coupled to a network link. A group is separated into multiple levels (logical or physical) that extend from input ports to output ports. Again, physical levels are not required but illustrated in the related figures for clarity only. Input data is first queued in a lowest level queue, and then the data is moved from level to level until the data is placed in an output queue for transmission or output via one of the output ports.
Data movement between levels of the class queues is controlled by a respective weight set where weights of the weight set are determined based on the desired characteristics that distinguish the classes. In this way, data of classes requiring greater bandwidth, for example, is moved through the class queues at a faster rate than data of classes having lower bandwidth requirements.
Each of the class queues may also be associated with buffer thresholds. The buffer thresholds specify a maximum size of a queue or a warning condition so that when an amount of data that is queued exceeds the buffer thresholds, either portions of the data may be dropped from the queue based on a data drop scheme or other queue management processes may be applied to adjust the queuing system. For example, the newest piece of data to be placed in the queue may be dropped or the weight set may be changed to account for the volume of data in the queue (e.g., by increasing queue throughput).
The class queuing system may use a weight based scheduling scheme to control transfer of data packets among queues. The weight sets may specify the data throughput for a queue during each cycle of the weight based scheduling so that appropriate transfer rates corresponding to the desired characteristics of each class may be achieved.